current가 None이 될 때까지 노드를 하나씩 방문한다
current가 한 노드 옮겨 갈 때마다 센 노드가 하나 늘고, current가 None이 되면 반복이 끝난다. 빈 리스트에서는 처음부터 current is None이다.
current = head · count = 0while current is not Nonecount += 1 · current = current.nextreturn count
현재 상태
current 이동 횟수
배열은 인덱스가 n에 도달하면 멈추지만, 연결리스트는 current가 None인지 확인한다. 반복 한 번이 노드 하나를 방문하므로 size(head)의 비용은 Θ(n)이다.
i번째 노드에 가려면 head부터 next를 i번 따라간다
head는 바로 참조할 수 있지만, 중간 위치에는 앞선 연결을 차례로 통과해야 하므로 i가 클수록 next 이동 횟수가 늘어난다.
next 이동 횟수
도달할 위치
노드의 주소가 연속적이지 않으므로 위치를 주소 계산으로 건너뛸 수 없다. head나 tail이 직접 가리키는 첫 노드와 마지막 노드에는 Θ(1)로 접근하지만, 가운데 i번째 노드는 head부터 따라가므로 Θ(1+i)다.